/*
 * @lc app=leetcode.cn id=85 lang=java
 *
 * [85] 最大矩形
 */

// @lc code=start
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int h = matrix.length;//高,行数
        int w = matrix[0].length;//宽，列数
        int[] heights = new int[w];//每行都要存一个结果
        int ans = 0;
        for (int i = 0; i < h; i++) {//从第一行开始
            for (int j = 0; j < w; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;//这个是累加的
                } else {
                    heights[j] = 0;//一旦不为1，直接清零
                }
            }
            ans = Math.max(ans, largestRectangleArea(heights));
        }
        return ans;
    }
    //84题的代码
    public int largestRectangleArea(int[] heights) {
        int temp[] = new int[heights.length+2];
        System.arraycopy(heights, 0, temp, 1, heights.length);
        //前后加一个0，方便处理，因为这样就不用考虑增序排列的情况。
        Stack<Integer> s = new Stack<>();
        int area=0;
        for(int i=0;i<temp.length;i++){
            while(!s.isEmpty() && temp[i]<temp[s.peek()] ){
                int h = temp[s.pop()];//拿到h
                //下一个才是左边第一个小于它的
                area = Math.max(area, h*(i-s.peek()-1));
            }
            s.push(i);
        }

        return area;

    }
}
// @lc code=end

